package 算法基础模板.chapter_01.双指针.sliding_window;

import java.util.HashMap;
import java.util.Map;

/**
 *
 * 567. 字符串的排列
 * 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
 *
 * 换句话说，第一个字符串的排列之一是第二个字符串的子串。
 *
 * 示例1:
 *
 * 输入: s1 = "ab" s2 = "eidbaooo"
 * 输出: True
 * 解释: s2 包含 s1 的排列之一 ("ba").
 *
 *
 * 示例2:
 *
 * 输入: s1= "ab" s2 = "eidboaoo"
 * 输出: False
 *
 *
 * 注意：
 *
 * 输入的字符串只包含小写字母
 * 两个字符串的长度都在 [1, 10,000] 之间
 *
 * <pre>
 *     {@code
 *     string s, t;
 *     // 在 s 中寻找 t 的「最小覆盖子串」
 *     int left = 0, right = 0;
 *     string res = s;
 *
 *     while(right < s.size()) {
 *         window.add(s[right]);
 *         right++;
 *         // 如果符合要求，移动 left 缩小窗口
 *         while (window 符合要求) {
 *             // 如果这个窗口的子串更短，则更新 res
 *             res = minLen(res, window);
 *             window.remove(s[left]);
 *             left++;
 *         }
 *     }
 *     return res;
 *     }
 * </pre>{
 *
 * }
 *
 * @author Summerday
 */
public class LC567 {
    public boolean checkInclusion(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        if(n > m) return false;

        Map<Character, Integer> needs = new HashMap<>();
        Map<Character, Integer> windows = new HashMap<>();
        for(int i = 0; i < n; i ++) {
            needs.put(s1.charAt(i), needs.getOrDefault(s1.charAt(i), 0) + 1);
        }

        int match = 0;

        int l = 0, r = 0;
        while(r < m){
            char c = s2.charAt(r);
            if(needs.containsKey(c)){
                windows.put(c, windows.getOrDefault(c, 0) + 1);
                if(windows.get(c).equals(needs.get(c))){
                    match ++;
                }
            }
            r ++;
            while(match == needs.keySet().size()){
                if(r - l == n) return true;
                char z = s2.charAt(l);

                if(needs.containsKey(z)){
                    windows.put(z, windows.get(z) - 1);
                    if(windows.get(z) < needs.get(z)){
                        match --;
                    }
                }
                l ++;
            }
        }
        return false;
    }

    public boolean checkInclusionArr(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        if(n > m) return false;

        int[] needs = new int[128];
        int[] windows = new int[128];
        int needLen = 0;
        for(int i = 0; i < n; i ++) {
            needs[s1.charAt(i)] ++;
        }
        // 表示有几类字母需要匹配
        for(int num : needs){
            if(num > 0) needLen ++;
        }

        int match = 0;

        int l = 0, r = 0;
        while(r < m){
            char c = s2.charAt(r);
            windows[c] ++;
            // 表示匹配一类字母
            if(windows[c] == needs[c]){
                match ++;
            }
            r ++;
            // 所有字母都匹配， 接下来缩小左边界
            while(match == needLen){
                // 长度和s1相等，就可以返回了
                if(r - l == n) return true;
                char z = s2.charAt(l);
                if(needs[z] > 0){
                    windows[z] --;
                    // 一直移到次数不够了，内循环就退出了
                    if(windows[z] < needs[z]) {
                        match --;
                    }
                }
                // 内循环不断操作左边界
                l ++;
            }
        }
        return false;
    }
}
